上一篇看到，陣列元素會連續存放在記憶體中。這個特性讓電腦可以透過索引直接找到指定元素，但也帶來一個限制：如果要在陣列中間插入或刪除資料，其他元素就可能必須跟著「搬家」。

這一篇會實際處理陣列的搜尋、插入與刪除，並比較它們的時間複雜度。

在陣列中搜尋資料

如果要在尚未排序的陣列中尋找某個數字，最直接的方法就是從第一個元素開始逐一比較。這種方法稱為線性搜尋（linear search）。

#include <stdio.h>

int main(void) {
    int scores[5] = {80, 90, 75, 60, 85};
    int target = 75;
    int foundIndex = -1;

    for (int i = 0; i < 5; i++) {
        if (scores[i] == target) {
            foundIndex = i;
            break;
        }
    }

    if (foundIndex == -1) {
        printf("找不到 %d\n", target);
    } else {
        printf("在索引 %d 找到 %d\n", foundIndex, target);
    }

    return 0;
}

這裡先把 foundIndex 設成 -1，表示尚未找到。由於合法索引一定從 0 開始，所以可以用 -1 代表搜尋失敗。

搜尋不只是確認某筆資料存不存在。找到它的索引後，才知道要從哪個位置修改或刪除資料。因此，搜尋常常是其他資料操作的第一步。

最好的情況下，目標就在第一個位置，只需要比較一次；最壞的情況下，目標在最後一個位置，或根本不存在，就必須檢查全部 n 個元素。這裡的 n 代表陣列中的有效資料數量，因此線性搜尋的時間複雜度是 O(n)。

線性搜尋的好處是簡單，而且不需要先將資料排序；缺點是資料越多，最壞情況下要比較的次數就越多。例如一百萬筆未排序資料，最壞可能要比較一百萬次。之後會學到二分搜尋等方法，利用資料的排列或結構縮小搜尋範圍。

容量不等於目前的資料數量

在實作插入與刪除之前，要先分清楚兩個概念：

• 容量（capacity）：陣列實際配置了幾個位置。
• 長度（length）：目前已經放入幾筆有效資料。

例如：

int numbers[6] = {10, 20, 30, 40};
int length = 4;

numbers 的容量是 6，但目前只有 4 筆有效資料，因此還有兩個位置可以使用。陣列本身沒有變長；插入只是用掉原本就已經預留的位置。

C 語言的普通陣列大小一旦確定，就不能直接擴大。如果六個位置都已經使用，就不能再直接放入第七筆資料。

插入時：從右往左搬

假設陣列的容量是 6，目前有 4 筆有效資料。如果要在索引 2，也就是 20 和 30 之間插入 99，必須先把後面的元素往右移動。以下示意圖中的 [ ] 代表該位置不屬於目前的有效資料：

索引：          0    1    2    3    4    5
插入前：      [10] [20] [30] [40] [   ] [   ]

1. numbers[4] = numbers[3]
   將 40 複製到索引 4
                [10] [20] [30] [40] [40] [   ]

2. numbers[3] = numbers[2]
   將 30 複製到索引 3，覆蓋原本的 40
                [10] [20] [30] [30] [40] [   ]

3. numbers[2] = 99
   用 99 覆蓋原本的 30
                [10] [20] [99] [30] [40] [   ]

4. length 從 4 增加為 5
   插入後（capacity = 6，length = 5）
                [10] [20] [99] [30] [40] [   ]

這裡說的「搬動」，在 C 語言中其實是用指派運算將數值複製到新位置，原位置不會自動清空。因此過程中暫時出現兩個 40 或兩個 30 是正常的；隨著後續指派覆蓋舊位置，最後就會得到正確的陣列。

移動時要從右往左處理：先移動 40，再移動 30。如果從左往右移，30 可能會先覆蓋 40，導致原本的資料遺失。

刪除時：從左往右補

如果要刪除索引 2 的 99，後面的元素就要逐一往左移，把空缺補起來：

索引：          0    1    2    3    4    5
刪除前：      [10] [20] [99] [30] [40] [   ]

1. numbers[2] = numbers[3]
   將 30 複製到索引 2，覆蓋要刪除的 99
                [10] [20] [30] [30] [40] [   ]

2. numbers[3] = numbers[4]
   將 40 複製到索引 3，覆蓋原本的 30
                [10] [20] [30] [40] [40] [   ]

3. length 從 5 減為 4
   刪除後（capacity = 6，length = 4）
                [10] [20] [30] [40] [   ] [   ]

刪除時同樣不會自動清空記憶體，而是用後面的數值依序覆蓋前面的位置。所以索引 4 最後仍然留著舊數值 40，但 length 減為 4 之後，程式只會把索引 0 到 3 視為有效資料。

搬動時要從左往右處理：先用 30 覆蓋 99，再用 40 覆蓋舊的 30。如果反過來從右往左，就可能先覆蓋掉稍後還需要使用的資料。

實作陣列的插入與刪除

下面的程式把插入和刪除寫成函式。函式成功時會回傳新的長度；如果容量不足或索引不合法，則回傳 -1。

#include <stdio.h>

#define CAPACITY 6

void printArray(const int numbers[], int length) {
    for (int i = 0; i < length; i++) {
        printf("%d ", numbers[i]);
    }
    printf("\n");
}

int insertAt(int numbers[], int length, int capacity,
             int index, int value) {
    if (length >= capacity || index < 0 || index > length) {
        return -1;
    }

    // 從右往左移，先騰出 index 的位置
    for (int i = length; i > index; i--) {
        numbers[i] = numbers[i - 1];
    }

    numbers[index] = value;
    return length + 1;
}

int deleteAt(int numbers[], int length, int index) {
    if (index < 0 || index >= length) {
        return -1;
    }

    // 從左往右移，用後面的元素補上空缺
    for (int i = index; i < length - 1; i++) {
        numbers[i] = numbers[i + 1];
    }

    return length - 1;
}

int main(void) {
    int numbers[CAPACITY] = {10, 20, 30, 40};
    int length = 4;

    printf("原本的陣列：");
    printArray(numbers, length);

    int newLength = insertAt(numbers, length, CAPACITY, 2, 99);
    if (newLength == -1) {
        printf("插入失敗\n");
        return 1;
    }
    length = newLength;

    printf("插入 99 之後：");
    printArray(numbers, length);

    newLength = deleteAt(numbers, length, 2);
    if (newLength == -1) {
        printf("刪除失敗\n");
        return 1;
    }
    length = newLength;

    printf("刪除索引 2 之後：");
    printArray(numbers, length);

    return 0;
}

程式輸出為：

原本的陣列：10 20 30 40
插入 99 之後：10 20 99 30 40
刪除索引 2 之後：10 20 30 40

insertAt() 允許 index == length，因為這代表把新資料加在最後面；deleteAt() 則要求 index < length，因為只能刪除已經存在的元素。

陣列常見操作的效率

以陣列中的有效資料數量 n 作為輸入規模，常見操作的時間複雜度如下：

插入或刪除最後一個元素時，可能不需要搬動其他資料；但在開頭或中間操作時，最壞情況下可能要搬動接近 n 個元素，因此通常以 O(n) 表示。

小結

陣列會把元素連續存放，所以可以透過索引快速取得指定元素。但同樣因為元素緊挨在一起，在中間插入或刪除資料時，後面的元素就必須跟著移動。

今日重點：

• 未排序陣列的線性搜尋，最壞情況需要檢查全部元素。
• 陣列的容量和目前的有效長度不一定相同。
• 插入時從右往左搬，才不會覆蓋尚未移動的資料。
• 刪除時從左往右補，再把有效長度減一。
• 線性搜尋、中間插入與中間刪除的時間複雜度通常是 O(n)。

下一篇會把陣列延伸到字串、二維陣列與矩陣，觀察資料從一排變成多排後，又會如何存放與處理。